package find.least.index.sum.of.two.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2019/12/20
 * @author 王光浩
 * @Need   给出两个数组，找出两个数组中都拥有且下标相加最小的元素值（如果有多个则全部返回）
 * @Method 使用HashMap来解决。
 *         思路：将一个数组中所有元素和下标加入到HashMap中，元素值为key，下标为value，然后循环遍历另一个数组找出元素
 *              值相同且下标和最小的元素，并将结果存储在result数组中。
 *         复杂度分析：时间复杂度O（n*x）——x是字符串长度，空间复杂度O（n*x）——x是字符串长度
 */
public class MyMethodTwo {
	public String[] findRestaurant(String[] list1, String[] list2) {
		Map<String,Integer> hashMap=new HashMap<String,Integer>();
		int list1Len=list1.length;
		int list2Len=list2.length;
	    int[] index=new int[list2Len]; //保存符合要求的元素在list2中的下标
	    int total=0;                   //保存index下一个元素值存储的下标
	    int minimum=list2Len+list1Len; //保存最小下标和  
	    //将list1加入到hashMap中
	    for(int i=0;i<list1Len;i++) {
	    	hashMap.put(list1[i], i);
	    }
	    //循环遍历list2，将符合要求的元素下标存放在index数组中
	    int tem;
	    for(int i=0;i<list2Len;i++) {
	    	//当元素值相等且下标和小于等于minimum
	    	if(hashMap.get(list2[i])!=null && (tem=hashMap.get(list2[i])+i)<=minimum) {
	    		if(tem<minimum) {
	    			total=0;
	    			minimum=tem;
	    		}
	    		index[total++]=i; //保存符合要求元素值的下标，然后将total++
	    	}
	    }
	    //获取符合题意的元素值，并使用字符串数组保存
	    String[] result=new String[total];
	    for(int i=0;i<total;i++) {
	    	result[i]=list2[index[i]];
	    }
	    return result;
	}
}
